package com.zwj.interview.回溯;

import java.util.LinkedList;
import java.util.List;

/**
 * 题目：输入一个正整数n，请输出所有包含n个左括号和n个右括号的组合，
 * 要求每个组合的左括号和右括号匹配。
 * 例如，当n等于2时，有两个符合条件的括号组合，分别是"（()）"和"()()"
 */
public class 生成匹配的括号 {

    public List<String> generateParenthesis(int n) {
        List<String> result = new LinkedList<>();
        helper(n, n, "", result);
        return result;
    }

    private void helper(int left, int right, String parenthesis, List<String> result) {
        /**
         * 参数left表示还需要生成左括号的数目，参数right表示还需要生成右括号的数目。每生成一个左括号，
         * 参数left减1；每生成一个右括号，参数right减1。当参数left和right都等于0时，一个完整的括号组合已经生成
         */
        if (left == 0 && right == 0) {
            result.add(parenthesis);
            return;
        }
        //在生成一个括号时，只要已经生成的左括号的数目少于n个（即参数left大于0）就可能生成一个左括号，
        if (left > 0) {
            helper(left - 1, right, parenthesis + "(", result);
        }
        //还需生成的左括号数小于还需生成的右括号时，说明选择差的是右括号，所以需要生成右括号
        if (left < right) {
            helper(left, right - 1, parenthesis + ")", result);
        }
    }
}
